package q15_threeSum;

import java.util.*;

public class Solution_1 {
    public static void main(String[] args) {

        List<List<Integer>> ll = threeSum(new int[]{});
        System.out.println(ll);
    }

    public static List<int[]> twoSumBeta(int[] nums, int target) {
        // 创建一个List用来存结果
        List<int[]> res = new ArrayList<>();

        Map<Integer, Integer> hashtable = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {

            if (hashtable.containsKey(target - nums[i])) {
                res.add(new int[]{target - nums[i],nums[i]});
            }
            hashtable.put(nums[i],i);
        }

        return res;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultF = new ArrayList<>();
        Set<Set<Integer>> result = new HashSet<>();

        // 判断三数之和
        // 使用哈希表来避免出现重复 比如1，0，-1，1 将会导致计算1，0，-1后进入下一个0时，又计入0，-1，1
        Map<Integer, Integer> hashtable = new HashMap<>();

        // Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {

            if (hashtable.containsKey(nums[i])) {
                // 重复数字，则跳过
                continue;
            }
            hashtable.put(nums[i],i);

            int[] bin = Arrays.copyOfRange(nums,i + 1,nums.length);
            if(twoSumBeta(bin, -nums[i]).size() > 0){
                for (int[] ints : twoSumBeta(bin, -nums[i])) {
                    // 是否考虑返回一个set使不重复
                    List<Integer> list = new ArrayList<>();

                    Collections.addAll(list,nums[i],ints[0],ints[1]);
                    Set<Integer> set = new HashSet<>(list);

                    if(!result.contains(set)){
                        result.add(set);
                        resultF.add(new ArrayList<>(list));
                    }

                }

            }
        }

        return resultF;
    }
}
